Text Quote Selectorでマーカーの位置を推定する

Text Quote Selectorは、Webページ上で選択したテキストを表現するためのデータ構造である。

データ構造

exact 選択したテキスト

prefix テキスト前方の数文字分

suffix テキスト後方の数文字分

ページの更新によってテキストの位置が変わった場合でも、その前後の文字も記録しているため位置を推定できる。

例えば http://example.com/ の This domain is for use ~ を選択したとき、以下のようなデータが記録される。

https://gyazo.com/d189f1b308f2b639c7d572dbc2a45538

exact domain

prefix \n\n Example Domain\n This

suffix is for use in illustrative exam

http://example.com/ にはdomainというテキストが複数回出てくる。

This domain is for use ~

this domain in literature ~

データからWebページ上のテキスト位置を推定するとき、This domain is ~ のほうが選択される。

複数のテキスト候補のうち、前後の文脈が最も一致する候補を優先する。

テキストの一致度は、レーベンシュタイン距離（編集距離）によって計算できる。

これは何文字追加・削除・置換すれば2つの文字列が一致するか、を表す量である。

例えばkittenとsittingのレーベンシュタイン距離は3と計算される。

kittenに対して以下3つの操作をすることで、文字列が一致するためである。

kをsに置換

eをiを置換

末尾にgを追加

テキストを選択するアルゴリズムは以下のとおり。

exactに完全一致するテキストを複数検索する。

見つかった複数のテキスト候補に対して、前後のレーベンシュタイン距離を計算する。

テキストの前方と、prefixの距離

テキストの後方と、suffixの距離

距離の合計が最小となるテキストを選択する。

annoでは、ユーザーが引いたマーカーの位置を記録するためにText Quote Selectorを利用している。